package leetcode

//https://leetcode.com/problems/regular-expression-matching
/**
 * 正则匹配
 * 这道题目需要以 p 为基准在 目标字符串中寻找匹配项，而不是以目标串为基准在 p 中寻找匹配
 * 1)p 为空 ，如果 s 为空返回 true，反之返回 false
 * 2)p 长度为1 p为. 或者 p 和 s 相等返回true ,其余返回false
 * 3)p 长度为2及以上————————————————————>
 *
- 若 p 的第二个字符为 * ，进行下列循环，条件是若 s 不为空且首字符匹配（包括p[0]为 . ），调用递归函数匹配s和去掉前两个字符的 p
（这样做的原因是假设此时的星号的作用是让前面的字符出现 0 次，验证是否匹配），
若匹配返回 true，否则s去掉首字母（因为此时首字母匹配了，我们可以去掉s的首字母，
而p由于星号的作用，可以有任意个首字母，所以不需要去掉），继续进行循环。 [这一步是整个的关键，巧妙的解决如何在零次匹配 和多次匹配之间选择 ]

- 返回调用递归函数匹配s和去掉前两个字符的p的结果（这么做的原因是处理星号无法匹配的内容，
比如 s="ab", p = "a*b"，直接进入 while 循环后，我们发现"ab"和"b"不匹配，所以 s 变成 "b"，
那么此时跳出循环后，就到最后的 return 来比较 "b"和 "b" 了，返回 true。再举个例子，
比如 s = "", p = "a*"，由于 s 为空，不会进入任何的 if 和 while，只能到最后的 return 来比较了，返回 true，正确）。
 */


class RegularExpressionMatching {


    fun isMatch(s: String, p: String): Boolean {

        if (p.isEmpty()) return s.isEmpty()

        if (p.length == 1) return s == p || (s.length == 1 && p[0] == '.')

        // 如果 p[1] !='*'
        if (p[1] != '*')
            return when {
                s.isEmpty() -> false
                p[0] == s[0] || p[0] == '.' -> isMatch(s.substring(1), p.substring(1))
                else -> false
            }
        else {
            var ss = s


            //while 循环，反复尝试 去掉首字母和* 之后是否可以匹配，否则去掉s的首字母直到首字母不匹配为止进入下一次递归
            while (ss.isNotEmpty() && (ss[0] == p[0] || p[0] == '.')) {
                if (isMatch(ss, p.substring(2))) return true
                ss = ss.substring(1)
            }

            //最后处理 s 为空或、
            return isMatch(ss, p.substring(2))
        }
    }


}

fun main(args: Array<String>) {
    println(RegularExpressionMatching().isMatch("aa", "a*"))
}
